<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0"><title>我的第一篇文章 | 狼族少年、血狼</title><meta name="author" content="狼族少年、血狼"><meta name="copyright" content="狼族少年、血狼"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="重新安排行程题目描述给你一份😂😁🤣😂😋😍航线列表 tickets ，其中 tickets[i] &#x3D; [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。  例如，行程 [“JFK”, “LG">
<meta property="og:type" content="article">
<meta property="og:title" content="我的第一篇文章">
<meta property="og:url" content="https://geekwolfman.github.io/2023/03/22/%E6%88%91%E7%9A%84%E7%AC%AC%E4%B8%80%E7%AF%87%E6%96%87%E7%AB%A0.html">
<meta property="og:site_name" content="狼族少年、血狼">
<meta property="og:description" content="重新安排行程题目描述给你一份😂😁🤣😂😋😍航线列表 tickets ，其中 tickets[i] &#x3D; [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。  例如，行程 [“JFK”, “LG">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://lyj--blog.oss-cn-chengdu.aliyuncs.com/config/040ee022f96e9b71ff7aec4ec49fa22e.jpg">
<meta property="article:published_time" content="2023-03-22T08:42:48.000Z">
<meta property="article:modified_time" content="2023-03-22T15:03:54.454Z">
<meta property="article:author" content="狼族少年、血狼">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://lyj--blog.oss-cn-chengdu.aliyuncs.com/config/040ee022f96e9b71ff7aec4ec49fa22e.jpg"><link rel="shortcut icon" href="http://www.geekwolfman.xyz/images/head-portrait/head-portrait.jpg"><link rel="canonical" href="https://geekwolfman.github.io/2023/03/22/%E6%88%91%E7%9A%84%E7%AC%AC%E4%B8%80%E7%AF%87%E6%96%87%E7%AB%A0.html"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: {"path":"/db.json","preload":false,"languages":{"hits_empty":"找不到您查询的内容：${query}"}},
  translate: undefined,
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isAnchor: false,
  percent: {
    toc: true,
    rightside: false,
  }
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '我的第一篇文章',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2023-03-22 23:03:54'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
    win.getCSS = (url,id = false) => new Promise((resolve, reject) => {
      const link = document.createElement('link')
      link.rel = 'stylesheet'
      link.href = url
      if (id) link.id = id
      link.onerror = reject
      link.onload = link.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        link.onload = link.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(link)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const detectApple = () => {
      if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    })(window)</script><meta name="generator" content="Hexo 6.3.0"></head><body><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/pace-js/themes/blue/pace-theme-minimal.min.css"/><script src="https://cdn.jsdelivr.net/npm/pace-js/pace.min.js"></script><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="http://www.geekwolfman.xyz/images/head-portrait/head-portrait.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">2</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">0</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">0</div></a></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-paper-plane"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('http://lyj--blog.oss-cn-chengdu.aliyuncs.com/config/040ee022f96e9b71ff7aec4ec49fa22e.jpg')"><nav id="nav"><span id="blog-info"><a href="/" title="狼族少年、血狼"><span class="site-name">狼族少年、血狼</span></a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search" href="javascript:void(0);"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-paper-plane"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">我的第一篇文章</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-03-22T08:42:48.000Z" title="发表于 2023-03-22 16:42:48">2023-03-22</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-03-22T15:03:54.454Z" title="更新于 2023-03-22 23:03:54">2023-03-22</time></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">2.2k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>8分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="我的第一篇文章"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h1 id="重新安排行程"><a href="#重新安排行程" class="headerlink" title="重新安排行程"></a>重新安排行程</h1><h2 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h2><p>给你一份😂😁🤣😂😋😍航线列表 tickets ，其中 tickets[i] &#x3D; [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。</p>
<p>所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。</p>
<ul>
<li>例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。</li>
</ul>
<p>假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。</p>
<p>示例1：</p>
<p><img src="https://assets.leetcode.com/uploads/2021/03/14/itinerary1-graph.jpg" alt="img"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：tickets = [[<span class="string">&quot;MUC&quot;</span>,<span class="string">&quot;LHR&quot;</span>],[<span class="string">&quot;JFK&quot;</span>,<span class="string">&quot;MUC&quot;</span>],[<span class="string">&quot;SFO&quot;</span>,<span class="string">&quot;SJC&quot;</span>],[<span class="string">&quot;LHR&quot;</span>,<span class="string">&quot;SFO&quot;</span>]]</span><br><span class="line">输出：[<span class="string">&quot;JFK&quot;</span>,<span class="string">&quot;MUC&quot;</span>,<span class="string">&quot;LHR&quot;</span>,<span class="string">&quot;SFO&quot;</span>,<span class="string">&quot;SJC&quot;</span>]</span><br></pre></td></tr></table></figure>

<p>示例 2：</p>
<p><img src="https://assets.leetcode.com/uploads/2021/03/14/itinerary2-graph.jpg" alt="img"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：tickets = [[<span class="string">&quot;JFK&quot;</span>,<span class="string">&quot;SFO&quot;</span>],[<span class="string">&quot;JFK&quot;</span>,<span class="string">&quot;ATL&quot;</span>],[<span class="string">&quot;SFO&quot;</span>,<span class="string">&quot;ATL&quot;</span>],[<span class="string">&quot;ATL&quot;</span>,<span class="string">&quot;JFK&quot;</span>],[<span class="string">&quot;ATL&quot;</span>,<span class="string">&quot;SFO&quot;</span>]]</span><br><span class="line">输出：[<span class="string">&quot;JFK&quot;</span>,<span class="string">&quot;ATL&quot;</span>,<span class="string">&quot;JFK&quot;</span>,<span class="string">&quot;SFO&quot;</span>,<span class="string">&quot;ATL&quot;</span>,<span class="string">&quot;SFO&quot;</span>]</span><br><span class="line">解释：另一种有效的行程是 [<span class="string">&quot;JFK&quot;</span>,<span class="string">&quot;SFO&quot;</span>,<span class="string">&quot;ATL&quot;</span>,<span class="string">&quot;JFK&quot;</span>,<span class="string">&quot;ATL&quot;</span>,<span class="string">&quot;SFO&quot;</span>] ，但是它字典排序更大更靠后。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><p>1 &lt;&#x3D; tickets.length &lt;&#x3D; 300</p>
</li>
<li><p>tickets[i].length &#x3D;&#x3D; 2</p>
</li>
<li><p>fromi.length &#x3D;&#x3D; 3</p>
</li>
<li><p>toi.length &#x3D;&#x3D; 3</p>
</li>
<li><p>fromi 和 toi 由大写英文字母组成</p>
</li>
<li><p>fromi !&#x3D; toi</p>
</li>
</ul>
<h2 id="自己的解"><a href="#自己的解" class="headerlink" title="自己的解"></a>自己的解</h2><h3 id="方法一：回溯法"><a href="#方法一：回溯法" class="headerlink" title="方法一：回溯法"></a>方法一：回溯法</h3><h4 id="思路"><a href="#思路" class="headerlink" title="思路"></a>思路</h4><p>比较经典的回溯题目，思路在代码中。</p>
<h4 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> List&lt;String&gt; <span class="title function_">findItinerary</span><span class="params">(List&lt;List&lt;String&gt;&gt; tickets)</span> &#123;</span><br><span class="line">        List&lt;String&gt; result = <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;();</span><br><span class="line">        HashMap&lt;String, List&lt;String&gt;&gt; map = <span class="keyword">new</span> <span class="title class_">HashMap</span>&lt;&gt;();</span><br><span class="line">        <span class="comment">//预处理，将当前节点的可行路径做映射</span></span><br><span class="line">        <span class="keyword">for</span> (List&lt;String&gt; ticket : tickets) &#123;</span><br><span class="line">            <span class="type">String</span> <span class="variable">t</span> <span class="operator">=</span> ticket.get(<span class="number">0</span>);</span><br><span class="line">            <span class="type">String</span> <span class="variable">d</span> <span class="operator">=</span> ticket.get(<span class="number">1</span>);</span><br><span class="line">            List&lt;String&gt; list = map.getOrDefault(t, <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;());</span><br><span class="line">            list.add(d);</span><br><span class="line">            map.put(t, list);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//将可行路径排序，优先选择最小的路径</span></span><br><span class="line">        map.values().forEach(x -&gt; x.sort(String::compareTo));</span><br><span class="line">        result.add(<span class="string">&quot;JFK&quot;</span>);</span><br><span class="line">        <span class="comment">//dfs返回值代表是否已找到最小路径</span></span><br><span class="line">        dfs(tickets, map, result, <span class="string">&quot;JFK&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="type">boolean</span> <span class="title function_">dfs</span><span class="params">(List&lt;List&lt;String&gt;&gt; tickets, HashMap&lt;String, List&lt;String&gt;&gt; map, List&lt;String&gt; result, String target)</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (result.size() == tickets.size() + <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        List&lt;String&gt; targetList = map.get(target);</span><br><span class="line">        <span class="comment">//需要判断是否为空</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; targetList != <span class="literal">null</span> &amp;&amp; i &lt; targetList.size(); i++) &#123;</span><br><span class="line">            <span class="type">String</span> <span class="variable">d</span> <span class="operator">=</span> targetList.get(i);</span><br><span class="line">            <span class="keyword">if</span> (!<span class="string">&quot;#&quot;</span>.equals(d)) &#123;</span><br><span class="line">                result.add(d);</span><br><span class="line">                <span class="comment">//将当前的路径设置为&quot;#&quot;代表已经访问过</span></span><br><span class="line">                targetList.set(i, <span class="string">&quot;#&quot;</span>);</span><br><span class="line">                <span class="keyword">if</span> (dfs(tickets, map, result, d)) &#123;</span><br><span class="line">                    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                targetList.set(i, d);</span><br><span class="line">                result.remove(result.size() - <span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="结果"><a href="#结果" class="headerlink" title="结果"></a>结果</h4><p>执行用时：6 ms, 在所有 Java 提交中击败了90.19%的用户</p>
<p>内存消耗：42.2 MB, 在所有 Java 提交中击败了5.62%的用户</p>
<h2 id="参考答案"><a href="#参考答案" class="headerlink" title="参考答案"></a>参考答案</h2><h3 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h3><p>本题和<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/cracking-the-safe/">753. 破解保险箱</a>类似，是力扣平台上为数不多的求解欧拉回路&#x2F;欧拉通路的题目。读者可以配合着进行练习。</p>
<p>我们化简本题题意:给定一个n个点m条边的图，要求从指定的顶点出发，经过所有的边恰好一次(可以理解为给定起点的「一笔画」问题)，使得路径的字典序最小。<br>这种「一笔画」问题与欧拉图或者半欧拉图有着紧密的联系，下面给出定义:。通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。</p>
<ul>
<li><p>通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。·具有欧拉回路的无向图称为欧拉图。</p>
</li>
<li><p>具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。</p>
</li>
</ul>
<p>因为本题保证至少存在一种合理的路径，也就告诉了我们，这张图是一个欧拉图或者半欧拉图。我们只需要输出这条欧拉诵路的路径即可。</p>
<blockquote>
<p>如果没有保证至少存在一种合理的路径，我们需要判别这张图是否是欧拉图或者半欧拉图，具体地:</p>
<ul>
<li><p>对于无向图G，G是欧拉图当且仅当G是连通的且没有奇度顶点。</p>
</li>
<li><p>对于无向图G，G是半欧拉图当且仅当G是连通的且G中恰有2个奇度顶点。</p>
</li>
<li><p>对于有向图G，G是欧拉图当且仅当G的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。</p>
<ul>
<li>对于有向图G，G是半欧拉图当且仅当G的所有顶点属于同一个强连通分量目</li>
<li>恰有一个顶点的出度与入度差为1;</li>
<li>恰有一个顶点的入度与出度差为1;。所有其他顶点的入度和出度相同。</li>
</ul>
</li>
</ul>
</blockquote>
<p>让我们考虑下面的这张图：</p>
<p><img src="/images/quote-images/3208e4e6255f4b1bb333dc066360661f.jpg"></p>
<p>我们从起点JFK出发，合法路径有两条：</p>
<ul>
<li><p>JFK →AAA →JFK →BBB →JFK</p>
</li>
<li><p>JFK →BBB →JFK →AAA →JFK</p>
</li>
</ul>
<p>既然要求字典序最小，那么我们每次应该贪心地选择当前节点所连的节点中字典序最小的那一个，并将其入栈。最后栈中就保存了我们遍历的顺序。</p>
<p>为了保证我们能够快速找到当前节点所连的节点中字典序最小的那一个，我们可以使用优先队列存储当前节点所连到的点，每次我们O(1)地找到最小字典序的节点，并O(log m)地删除它。</p>
<p>然后我们考虑一种特殊情况:</p>
<p><img src="/images/quote-images/b8c6de199cf14b2ca1370f65d23f6259.jpg"></p>
<p>当我们先访问AAA时，我们无法回到JFK，这样我们就无法访问剩余的边了。</p>
<p>也就是说，当我们贪心地选择字典序最小的节点前进时，我们可能先走入「死胡同」，从而导致无法遍历到其他还未访问的边。于是我们希望能够遍历完当前节点所连接的其他节点后再进入「死胡同」。</p>
<blockquote>
<p>注意对于每一个节点，它只有最多一个「死胡同」分支。依据前言中对于半欧拉图的描述，只有那个入度与出度差为1的节点会导致死胡同。</p>
</blockquote>
<h3 id="方法一：Hierholzer-算法"><a href="#方法一：Hierholzer-算法" class="headerlink" title="方法一：Hierholzer 算法"></a>方法一：Hierholzer 算法</h3><h4 id="思路-1"><a href="#思路-1" class="headerlink" title="思路"></a>思路</h4><p>Hierholzer 算法用于在连通图中寻找欧拉路径，其流程如下:</p>
<ul>
<li><p>从起点出发，进行深度优先搜索。</p>
</li>
<li><p>每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。</p>
</li>
<li><p>如果没有可移动的路径，则将所在节点加入到栈中，并返回。</p>
</li>
</ul>
<p>当我们顺序地考虑该问题时，我们也许很难解决该问题，因为我们无法判断当前节点的哪一个分支是「死胡同」分支。</p>
<p>不妨倒过来思考。我们注意到只有那个入度与出度差为1的节点会导致死胡同。而该节点必然是最后一个遍历到的节点。我们可以改变入栈的规则，当我们遍历完一个节点所连的所有节点后，我们才将该节点入栈(即逆序入栈)。</p>
<p>对于当前节点而言，从它的每一个非「死胡同」分支出发进行深度优先搜索，都将会搜回到当前节点。而从它的「死胡同」分支出发进行深度优先搜索将不会搜回到当前节点。也就是说当前节点的死胡同分支将会优先于其他非「死胡同」分支入栈。</p>
<p>这样就能保证我们可以「一笔画」地走完所有边，最终的栈中逆序地保存了「一笔画」的结果。我们只要将栈中的内容反转，即可得到答案。</p>
<h4 id="代码-1"><a href="#代码-1" class="headerlink" title="代码"></a>代码</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line">    Map&lt;String, PriorityQueue&lt;String&gt;&gt; map = <span class="keyword">new</span> <span class="title class_">HashMap</span>&lt;String, PriorityQueue&lt;String&gt;&gt;();</span><br><span class="line">    List&lt;String&gt; itinerary = <span class="keyword">new</span> <span class="title class_">LinkedList</span>&lt;String&gt;();</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> List&lt;String&gt; <span class="title function_">findItinerary</span><span class="params">(List&lt;List&lt;String&gt;&gt; tickets)</span> &#123;</span><br><span class="line">        <span class="keyword">for</span> (List&lt;String&gt; ticket : tickets) &#123;</span><br><span class="line">            <span class="type">String</span> <span class="variable">src</span> <span class="operator">=</span> ticket.get(<span class="number">0</span>), dst = ticket.get(<span class="number">1</span>);</span><br><span class="line">            <span class="keyword">if</span> (!map.containsKey(src)) &#123;</span><br><span class="line">                map.put(src, <span class="keyword">new</span> <span class="title class_">PriorityQueue</span>&lt;String&gt;());</span><br><span class="line">            &#125;</span><br><span class="line">            map.get(src).offer(dst);</span><br><span class="line">        &#125;</span><br><span class="line">        dfs(<span class="string">&quot;JFK&quot;</span>);</span><br><span class="line">        Collections.reverse(itinerary);</span><br><span class="line">        <span class="keyword">return</span> itinerary;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">dfs</span><span class="params">(String curr)</span> &#123;</span><br><span class="line">        <span class="keyword">while</span> (map.containsKey(curr) &amp;&amp; map.get(curr).size() &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="type">String</span> <span class="variable">tmp</span> <span class="operator">=</span> map.get(curr).poll();</span><br><span class="line">            dfs(tmp);</span><br><span class="line">        &#125;</span><br><span class="line">        itinerary.add(curr);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">作者：LeetCode-Solution</span><br><span class="line">链接：https:<span class="comment">//leetcode-cn.com/problems/reconstruct-itinerary/solution/zhong-xin-an-pai-xing-cheng-by-leetcode-solution/</span></span><br><span class="line">来源：力扣（LeetCode）</span><br><span class="line">著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。</span><br></pre></td></tr></table></figure>

<h4 id="复杂度分析"><a href="#复杂度分析" class="headerlink" title="复杂度分析"></a>复杂度分析</h4><p>时间复杂度:O(m log m)，其中 m是边的数量。对于每一条边我们需要O(log m)地删除它，最终的答案序列长度为m+1，而与n无关。</p>
<p>空间复杂度:O(m)，其中m是边的数量。我们需要存储每—条边。</p>
<blockquote>
<p>题解中 <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reconstruct-itinerary/solution/javadfsjie-fa-by-pwrliang/">DFS解法</a> 这个答案也很清晰！！！</p>
</blockquote>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href>狼族少年、血狼</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://geekwolfman.github.io/2023/03/22/%E6%88%91%E7%9A%84%E7%AC%AC%E4%B8%80%E7%AF%87%E6%96%87%E7%AB%A0.html">https://geekwolfman.github.io/2023/03/22/我的第一篇文章.html</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://geekwolfman.github.io" target="_blank">狼族少年、血狼</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"></div><div class="post_share"><div class="social-share" data-image="http://lyj--blog.oss-cn-chengdu.aliyuncs.com/config/040ee022f96e9b71ff7aec4ec49fa22e.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="next-post pull-full"><a href="/2023/03/22/hello-world.html" title="Hello World"><img class="cover" src="http://lyj--blog.oss-cn-chengdu.aliyuncs.com/config/745b610f94e6878a78a76860da345def.png" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">Hello World</div></div></a></div></nav></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="http://www.geekwolfman.xyz/images/head-portrait/head-portrait.jpg" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">狼族少年、血狼</div><div class="author-info__description"></div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">2</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">0</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">0</div></a></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/geekwolfman"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="mailto:2370032534@gmail.com" target="_blank" title="Email"><i class="fas fa-envelope"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">本站所有博文均是博主的学习笔记与个人理解，来源于网络，如有<span style="color:red;font-weight:bold;">侵权</span>请<span style="color:#49B1F5;text-decoration:underline;padding:0 1px;font-weight:bold">联系我</span>进行删除🥰。</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B"><span class="toc-number">1.</span> <span class="toc-text">重新安排行程</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="toc-number">1.1.</span> <span class="toc-text">题目描述</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%87%AA%E5%B7%B1%E7%9A%84%E8%A7%A3"><span class="toc-number">1.2.</span> <span class="toc-text">自己的解</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%96%B9%E6%B3%95%E4%B8%80%EF%BC%9A%E5%9B%9E%E6%BA%AF%E6%B3%95"><span class="toc-number">1.2.1.</span> <span class="toc-text">方法一：回溯法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF"><span class="toc-number">1.2.1.1.</span> <span class="toc-text">思路</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81"><span class="toc-number">1.2.1.2.</span> <span class="toc-text">代码</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%BB%93%E6%9E%9C"><span class="toc-number">1.2.1.3.</span> <span class="toc-text">结果</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E7%AD%94%E6%A1%88"><span class="toc-number">1.3.</span> <span class="toc-text">参考答案</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%89%8D%E8%A8%80"><span class="toc-number">1.3.1.</span> <span class="toc-text">前言</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%96%B9%E6%B3%95%E4%B8%80%EF%BC%9AHierholzer-%E7%AE%97%E6%B3%95"><span class="toc-number">1.3.2.</span> <span class="toc-text">方法一：Hierholzer 算法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-1"><span class="toc-number">1.3.2.1.</span> <span class="toc-text">思路</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81-1"><span class="toc-number">1.3.2.2.</span> <span class="toc-text">代码</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-number">1.3.2.3.</span> <span class="toc-text">复杂度分析</span></a></li></ol></li></ol></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/2023/03/22/%E6%88%91%E7%9A%84%E7%AC%AC%E4%B8%80%E7%AF%87%E6%96%87%E7%AB%A0.html" title="我的第一篇文章"><img src="http://lyj--blog.oss-cn-chengdu.aliyuncs.com/config/040ee022f96e9b71ff7aec4ec49fa22e.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="我的第一篇文章"/></a><div class="content"><a class="title" href="/2023/03/22/%E6%88%91%E7%9A%84%E7%AC%AC%E4%B8%80%E7%AF%87%E6%96%87%E7%AB%A0.html" title="我的第一篇文章">我的第一篇文章</a><time datetime="2023-03-22T08:42:48.000Z" title="发表于 2023-03-22 16:42:48">2023-03-22</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2023/03/22/hello-world.html" title="Hello World"><img src="http://lyj--blog.oss-cn-chengdu.aliyuncs.com/config/745b610f94e6878a78a76860da345def.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Hello World"/></a><div class="content"><a class="title" href="/2023/03/22/hello-world.html" title="Hello World">Hello World</a><time datetime="2023-03-22T07:33:40.332Z" title="发表于 2023-03-22 15:33:40">2023-03-22</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2023 By 狼族少年、血狼</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><span class="scroll-percent"></span><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.umd.min.js"></script><div class="js-pjax"></div><script defer="defer" id="ribbon" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/dist/canvas-ribbon.min.js" size="150" alpha="0.6" zIndex="-1" mobile="false" data-click="false"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span>  数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><hr/><div id="local-search-results"></div></div></div><div id="search-mask"></div><script src="/js/search/local-search.js"></script></div></body></html>